1. Technical Field
This invention relates generally to methods for improving the reliability of content-addressable memory (CAM) using shadow CAM. It also relates more specifically to improving the reliability of high-speed telecommunications switching systems, routers, and databases. Reliability is improved by providing a second array of CAM, referred to as shadow CAM, and writing, reading, and searching both the primary CAM and the shadow CAM in parallel. The results of parallel searches of the primary and shadow CAMs are compared to see if they are identical. If the results are identical, then the search result is declared valid. Otherwise, corrective action is initiated.
2. Background
When searching computer memory, the item searched for is referred to as a comparand. The comparand may be data or the address for some data. Computer memory is searched using a comparand to which values in memory are compared as the search progresses. Content-addressable memory (CAM) is memory which, when searched with a comparand consisting of data, returns the address in CAM, if any, where the data of the comparand can be found. CAM is associative, so addresses of segments of data may also be found. CAM is distinct from traditional random access memory (RAM). RAM is searched for a comparand that is an address and the search returns the data found at that address. CAM is a hardware implementation requiring no software.
CAM is searched for a comparand that is data and CAM returns an address of that data. More precisely, the CAM search returns information about the physical location (herein after xe2x80x9cphysical addressxe2x80x9d) of the data in the CAM. A device called a priority encoder, often integrated with the CAM, translates that physical address into a logical address for use by a computer. A priority encoder is needed primarily because a CAM search may return more than one result when memory contains more than one copy of the data. The priority encoder determines which of these multiple results has priority. Priority encoders may have additional capabilities, as will be discussed below.
CAM is designed to be searched in parallel: the comparand is compared to the data at every address simultaneously. Because a search of CAM does not read or write the data at the searched-for address, and because the search is a parallel search, CAM searches are very fast. This makes CAM ideal for search-intensive applications such as databases, networking, data compression, cache management, telecommunications switches, routers and image processing. CAM technology has been known in the art for over a decade and is shown and described in U.S. Pat. No. 5,034,919 to Sasai (issued Jul. 23, 1991), the disclosure of which is hereby incorporated herein by reference.
The disadvantage of a CAM search is that, because the data is not read or written during the search, some errors go undetected and uncorrected. For example, if the comparand does not match any data written into the CAM, but corrupted data in the CAM does match the comparand, the search will return the address of the corrupted data. For a further example, if data otherwise matching the comparand has been corrupted, the search will return no address. Data corruption in memory can occur as a result of environmental factors. For example, cosmic rays can cause bits in memory to change state, thereby corrupting the data those bits represent. This problem is particularly troublesome for satellite applications. Electrostatic discharge can also corrupt data. The environmental factors are random. For applications requiring very high reliability, conventional CAM technologies present difficulties.
The present invention uses shadow CAM to improve the reliability of searching CAM. The shadow CAM is a duplicate of the primary CAM and is read, written, and searched identically to and in parallel with the primary CAM. After a search is executed, the search results for the primary and shadow CAM are compared. It is unlikely that random environmental influences would corrupt data in the same place on each of two CAM arrays. If the search results are identical, then there is a high likelihood that the data is not corrupted. If the search results are not identical, then some data is corrupted, and corrective action can be initiated.